/*
 *
 * FP-Growth
 * 刘洪轩 1200012712
 * 445421142 at qq dot com
 *
 */

// 诚实代码保证：
// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 在此，我感谢 XXX, …, XXX对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>

/* 最大项目数 */
#define MAXN 20000
/* 最大交易数 */
#define MAXM 200000
/* 最大输入大小 */
#define MAXP 2000000
/* 最大内存分配大小 */
#define MEM 30000000

/*
 * 预先开一个静态数组
 * 按栈的方式分配内存
 */
char stack[MEM];
int stack_top = MEM;
inline void *alloc(size_t k) {
  assert(stack_top - (long)k >= 0);
  return &stack[stack_top -= k];
}

/* fp树结点 左子右兄法建树 */
struct fpnode {
  /* 父指针，子指针，兄弟指针 */
  fpnode *father, *child, *bro;
  /* 链表中的后继结点 */
  fpnode *next;
  /* 结点对应的项目编号 (经过离散化的值) */
  int entry;
  /* 对应的交易数量 */
  int sum;
};

/* fp树 */
struct fptree {
  /* 对应的项目数量 */
  int item_size;
  /* 链表头 */
  fpnode **list_head;
  /* 树根 */
  fpnode *root;
};

/*
 * 初始化fp树结点
 */
fpnode *create_fpnode(fpnode *fa, int v)
{
  fpnode *k = (fpnode*) alloc(sizeof(fpnode));
  k->father = fa;
  k->child = NULL;
  k->bro = NULL;
  k->next = NULL;
  k->entry = v;
  k->sum = 0;
  return k;
}

/*
 * 返回结点p对应的值为v的子结点，若不存在则建立
 * 由于调用顺序有序，只需要检查最后插入的子结点即可
 */
fpnode *get_child(fptree *tr, fpnode *p, int v) {
  /* 判断最后插入的子结点值是否为v */
  if (p->child == NULL || p->child->entry != v) {
    fpnode *k = create_fpnode(p, v);
    /* 插入新节点进入链表 */
    k->next = tr->list_head[v];
    tr->list_head[v] = k;
    /* 插入新节点为当前结点的子结点 */
    k->bro = p->child;
    p->child = k;
  }
  /* 返回子结点 */
  return p->child;
}

/*
 * 初始化fp树，m为树中对应的项目总数
 */
fptree *create_fptree(int m)
{
  fptree *tr = (fptree*) alloc(sizeof(fptree));
  tr->item_size = m;
  tr->list_head = (fpnode**) alloc(sizeof(fpnode*) * m);
  memset(tr->list_head, 0, sizeof(fpnode*) * m);
  /* 添加空结点作为根 */
  tr->root = create_fpnode(NULL, -1);
  return tr;
}

/* 输入数据 */
int data[MAXP];
/* 输入数据中的每个交易在data中对应的起始位置 */
int trac_st[MAXM], trac_ed[MAXM];
/* 交易排序索引 */
int trac[MAXM];

/* 项目索引 */
int item[MAXN];
int pos[MAXN];
/* 项目出现次数计数 */
int count[MAXN];

/* 递归过程中已经选取的当前项集 */
int set[MAXN];
int nset;

/* 临时空间 */
int tmp_trac[MAXN];

/* 最小阙值 */
int minfreq;
/* 频繁项计数 */
int ans;

/* 是否以quiet模式运行 */
bool quiet;

/* sort用的比较函数 */
inline bool item_comp(int a, int b)
{
  return count[a] == count[b] ? a < b : count[a] > count[b];
}
bool trac_comp(int a, int b)
{
  for (int *i = data + trac_st[a], *j = data + trac_st[b];
    *i != -1 || *j != -1; ++i, ++j)
    if (*i != *j) return *i < *j;
  return false;
}

/*
 * 建立新fp树从而递归进行数据挖掘
 * tr为原fp树
 * cand为原fp树中的包含的项目
 * v为新加入当前项集的项目在cand中的编号
 */
void fpgrowth(fptree *tr, int v, int *cand)
{

  /* 将cand[v]加入当前项集 */
  set[nset++] = cand[v];
  /* 保存内存分配栈的栈顶位置 */
  int save_stack = stack_top;

  /*
   * 计算在cand[v]出现条件下
   * cand[0]到cand[v-1]的出现次数
   */
  memset(count, 0, sizeof(int) * v);
  for (fpnode *p = tr->list_head[v]; p != NULL; p = p->next) {
    int c = p->sum;
    for (fpnode *q = p->father; q->entry != -1; q = q->father) {
      assert(q->entry < v);
      count[q->entry] += c;
    }
  }

  /*
   * 排除出现次数小于最小阙值的项
   * 对满足要求的项建立索引存在item中
   * pos[i]表示cand[i]在item中的位置，不满足要求的项为-1
   */
  int nc = 0;
  for (int i = 0; i < v; ++i) if (count[i] >= minfreq) nc++;
  int *item = (int*) alloc(sizeof(int) * nc);
  nc = 0;
  for (int i = 0; i < v; ++i) if (count[i] >= minfreq) {
    item[nc] = cand[i];
    pos[i] = nc++;
  } else pos[i] = -1;

  /* 根据上述结果建立新的fp树 */
  fptree *tree = create_fptree(nc);
  for (fpnode *p = tr->list_head[v]; p != NULL; p = p->next) {
    int c = p->sum;
    int ntmp = 0;
    for (fpnode *q = p->father; q->entry != -1; q = q->father)
      if (pos[q->entry] >= 0) {
        assert(pos[q->entry] < nc);
        tmp_trac[ntmp++] = pos[q->entry];
      }
    fpnode *now = tree->root;
    now->sum += c;
    for (int j = ntmp - 1; j >= 0; --j) {
      now = get_child(tree, now, tmp_trac[j]);
      now->sum += c;
    }
  }

  /*
   * 新fp树中包含的交易数即为当前项集的支持度
   * 若大于等于最小阙值计数并输出
   */
  if (tree->root->sum >= minfreq) {
    ++ans;
    if (!quiet) {
      memcpy(tmp_trac, set, sizeof(int) * nset);
      std::sort(tmp_trac, tmp_trac + nset);
      for (int i = 0; i < nset; ++i) printf("%d ", tmp_trac[i]);
      printf(": %d\n", tree->root->sum);
    }
  }

  /* 递归继续挖掘 */
  for (int i = nc-1; i >= 0; --i)
    fpgrowth(tree, i, item);

  /* 恢复内存栈顶位置 */
  stack_top = save_stack;
  /* cand[v]从当前项集中删除 */
  --nset;

}

int main(int argc, char *argv[])
{

  double pp;
  int n = 0, m = 0, ndata = 0;

  /* 处理输入的参数 */
  pp = atof(argv[1]);
  quiet = argc > 2 && strcmp(argv[2], "-q") == 0;

  /* 读入输入数据 */
  int p = 0;
  while (true) {
    int ch;
    while (true) {
      ch = getchar();
      if (ch == -1) goto LoopEnd;
      if (ch == '\n') goto LoopContinue;
      if (ch <= '9' && ch >= '0') break;
    }
    ungetc(ch, stdin);

    trac_st[m] = p;
    while (true) {
      scanf("%d", &data[p]);
      if (data[p] >= n) n = data[p] + 1;
      ++p;
      while (true) {
        ch = getchar();
        if (ch == -1) {
          goto LoopEnd;
          data[p++] = -1;
          trac_ed[m++] = p;
        }
        if (ch == '\n') {
          data[p++] = -1;
          trac_ed[m++] = p;
          goto LoopContinue;
        }
        if (ch <= '9' && ch >= '0') break;
      }
      ungetc(ch, stdin);
    }
LoopContinue:;
  }
LoopEnd:

  assert(n <= MAXN);
  assert(m <= MAXM);
  assert(p <= MAXP);

  /* 计算阙值 */
  minfreq = (int) (m * pp + 1e-3);
  if (minfreq < 1) minfreq = 1;

  /*
   * 计算每个项目在每个交易中出现的次数
   * 并根据次数对项的索引进行排序
   */
  memset(count, 0, sizeof(count));
  for (int i = 0; i < p; ++i) if (data[i] >= 0) ++count[data[i]];
  for (int i = 0; i < n; ++i) item[i] = i;
  std::sort(item, item + n, item_comp);
  for (int i = 0; i < n; ++i) pos[item[i]] = i;

  /* 对所有交易建立索引并排序 */
  for (int i = 0; i < m; ++i) std::sort(data + trac_st[i], data + trac_ed[i], item_comp);
  for (int i = 0; i < m; ++i) trac[i] = i;
  std::sort(trac, trac + m, trac_comp);

  /* 排除出现次数小于最小阙值的项 */
  int nc = n;
  while (nc > 0 && count[item[nc-1]] < minfreq) --nc;

  /* 建立初始fp树 */
  fptree *tree = create_fptree(nc);
  for (int i = 0; i < m; ++i) {
    fpnode *now = tree->root;
    ++now->sum;
    for (int j = trac_st[trac[i]]; data[j] != -1; ++j) if (pos[data[j]] < nc) {
      now = get_child(tree, now, pos[data[j]]);
      assert(now->entry > now->father->entry);
      ++now->sum;
    }
  }

  /*
   * 对每一个项枚举加入集合
   * 在fp树上进行挖掘
   * 先选择出现次数少的项
   */
  nset = 0;
  ans = 0;
  for (int i = nc-1; i >= 0; --i)
    fpgrowth(tree, i, item);

  if (quiet) printf("%d\n", ans);

  return 0;
}
